package com.company.array;

import java.util.*;

/***
 *
 * https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/30/
 *
 * 有效的数独
 * 判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
 *
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
 *
 * 示例 1:
 *
 * 输入:
 * [
 *   ["5","3",".",".","7",".",".",".","."],
 *   ["6",".",".","1","9","5",".",".","."],
 *   [".","9","8",".",".",".",".","6","."],
 *   ["8",".",".",".","6",".",".",".","3"],
 *   ["4",".",".","8",".","3",".",".","1"],
 *   ["7",".",".",".","2",".",".",".","6"],
 *   [".","6",".",".",".",".","2","8","."],
 *   [".",".",".","4","1","9",".",".","5"],
 *   [".",".",".",".","8",".",".","7","9"]
 * ]
 * 输出: true
 *
 *
 * 示例 2:
 *
 * 输入:
 * [
 *   ["8","3",".",".","7",".",".",".","."],
 *   ["6",".",".","1","9","5",".",".","."],
 *   [".","9","8",".",".",".",".","6","."],
 *   ["8",".",".",".","6",".",".",".","3"],
 *   ["4",".",".","8",".","3",".",".","1"],
 *   ["7",".",".",".","2",".",".",".","6"],
 *   [".","6",".",".",".",".","2","8","."],
 *   [".",".",".","4","1","9",".",".","5"],
 *   [".",".",".",".","8",".",".","7","9"]
 * ]
 * 输出: false
 * 解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
 *      但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
 *
 *
 */
public class IsValidSudoku {

    public static void main(String[] args) {
        IsValidSudoku isValidSudoku = new IsValidSudoku();

        char[][] shudu = {
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };

        boolean validSudoku = isValidSudoku.isValidSudoku(shudu);

        System.out.println("validSudoku = " + validSudoku);

    }

    /***
     * 思路
     *
     * 1.先判断每一个横轴的数字是否有相同的，
     * 2.然后判断每一个竖轴是否有数字相同。
     * 3.然后判断附近相邻的9个数是否有相同的
     *
     * @param board
     * @return
     */
    public boolean isValidSudoku2(char[][] board) {

        int len = board.length;

        for (int i = 0; i < len; i++) {
            //1.先检查横轴
            int[] row = new int[len];
            int[] column = new int[len];
            int[] nineNumber = new int[len];

            for (int j = 0; j < len; j++) {
                row[j] = (int) board[i][j];
                column[j] = board[j][i];
                int x = i / 3 * 3 + j / 3; //横轴上的坐标计算
                int y = i % 3 * 3 + j % 3; //处于竖轴上的坐标计算
                nineNumber[j] = board[x][y];
                System.out.print(nineNumber[j] + " ");
            }

            System.out.println();
            if (checkSameNumber(row)) {
                System.out.println("横轴出现重复 i = " + i);
                return false;
            }

            if (checkSameNumber(column)) {
                System.out.println("竖轴出现重复 i = " + i);
                return false;
            }

            if (checkSameNumber(nineNumber)) {
                System.out.println("九宫格内出现重复数据 i = " + i);
                return false;
            }

            //3.3*3九宫格
//            {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
//            {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
//            {'.', '9', '8', '.', '.', '.', '.', '6', '.'},

//            {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
//            {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
//            {'7', '.', '.', '.', '2', '.', '.', '.', '6'},

//            {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
//            {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
//            {'.', '.', '.', '.', '8', '.', '.', '7', '9'}


//第一组数据
//            [0][0]   [0][1]      [0][2]           ---------          [0][3]   [0][4]      [0][5]
//
//            [1][0]   [1][1]      [1][2]           ---------          [1][3]   [1][4]      [1][5]
//
//            [2][0]   [2][1]      [2][2]           ---------          [2][3]   [2][4]      [2][5]
//---------------------------------------           ---------          -----------------------------------------
//            [3][0]   [3][1]      [3][2]           ---------          [3][3]   [3][4]      [3][5]

//            [4][0]   [4][1]      [4][2]           ---------          [4][3]   [2][4]      [2][5]

//            [5][0]   [5][1]      [5][2]           ---------          [5][3]   [2][4]      [2][5]


        }

        return true;
    }

    /***
     * 方法二
     * @param board
     * @return
     */
    public boolean isValidSudoku(char[][] board) {

        int len = board.length;

        for (int i = 0; i < len; i++) {
            //1.先检查横轴
            Map<Integer, Integer> rowMap = new HashMap<>();
            Map<Integer, Integer> clow = new HashMap<>();
            Map<Integer, Integer> nine = new HashMap<>();

            for (int j = 0; j < len; j++) {

                int x = i / 3 * 3 + j / 3; //横轴上的坐标计算
                //y的偏移计算
                int y = i % 3 * 3 + j % 3; //处于竖轴上的坐标计算

                if (rowMap.containsKey((int)board[i][j]) && rowMap.get((int)board[i][j])!=46) {
                    return false;
                }

                if (clow.containsKey((int)board[j][i]) && clow.get((int)board[j][i])!=46) {
                    return false;
                }

                if (nine.containsKey((int)board[x][y]) && nine.get((int)board[x][y])!=46) {
                    return false;
                }

                rowMap.put((int) board[i][j], (int) board[i][j]);
                clow.put((int) board[j][i], (int) board[j][i]);
                nine.put((int) board[x][y], (int) board[x][y]);

            }


            //3.3*3九宫格
//            {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
//            {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
//            {'.', '9', '8', '.', '.', '.', '.', '6', '.'},

//            {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
//            {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
//            {'7', '.', '.', '.', '2', '.', '.', '.', '6'},

//            {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
//            {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
//            {'.', '.', '.', '.', '8', '.', '.', '7', '9'}


//第一组数据
//            [0][0]   [0][1]      [0][2]           ---------          [0][3]   [0][4]      [0][5]
//
//            [1][0]   [1][1]      [1][2]           ---------          [1][3]   [1][4]      [1][5]
//
//            [2][0]   [2][1]      [2][2]           ---------          [2][3]   [2][4]      [2][5]
//---------------------------------------           ---------          -----------------------------------------
//            [3][0]   [3][1]      [3][2]           ---------          [3][3]   [3][4]      [3][5]

//            [4][0]   [4][1]      [4][2]           ---------          [4][3]   [2][4]      [2][5]

//            [5][0]   [5][1]      [5][2]           ---------          [5][3]   [2][4]      [2][5]


        }

        return true;
    }

    /***
     * 检查是否有重复的数据
     * @param numbers
     * @return
     */
    public boolean checkSameNumber(int[] numbers) {
        Map<Integer, Integer> map = new HashMap<>();

        for (Integer number : numbers) {
            if (number == 46) continue;

            if (map.containsKey(number)) {
                System.out.println("重复数字为 = " + number);
                return true;
            } else {
                map.put(number, number);
            }
        }
        return false;

    }
}
